package io.tec.cloud.algorithm.c06_v20220623;

import io.tec.cloud.algorithm.AlgorithmUtil;

import java.util.Arrays;

public class T43_HeapSort {

    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

//        for (int i = 1; i < arr.length; i++) {
//            heapInsert(arr, i);
//        }

        // 数组长度
        for (int i = arr.length - 1; i >= 0; i--) {
            heapify(arr, i, arr.length);
        }

        // 最大索引
//        for (int i = arr.length - 1; i >= 0; i--) {
//            heapify(arr, i, arr.length - 1);
//        }

        // 数组长度
        int heapSize = arr.length;
        while (heapSize > 1) {
            // 固定一个索引位置：0和数组最后一个位置交换
            AlgorithmUtil.swap(arr, 0, heapSize - 1);
            // 从0位置，看是否能往下移动，--heapSize为数组长度，因为不可到达，所以left < heapSize。
            heapify(arr, 0, --heapSize);
        }
        // 最大索引
//        int heapSize = arr.length - 1;
//        while (heapSize > 0) {
//            // 固定一个索引位置：0和数组最后一个位置交换
//            AlgorithmUtil.swap(arr, 0, heapSize);
//            // 从0位置，看是否能往下移动，--heapSize为最大索引，因为要比较和左节点的大小，即左节点可以达到，所以left <= heapSize。
//            heapify(arr, 0, --heapSize);
//        }
    }

    /**
     * 从arr[index]位置的数，能否往下移动
     *
     * @param arr
     * @param index
     * @param heapSize
     */
    private static void heapify(int[] arr, int index, int heapSize) {
        int left = (index * 2) + 1;
        // TODO  一直下沉到底
        while (left < heapSize) {
            // TODO 右结点边界和左结点一致：同<或者<=
            int largerIndex = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            largerIndex = arr[largerIndex] > arr[index] ? largerIndex : index;
            if (largerIndex == index) {
                return;
            }
            AlgorithmUtil.swap(arr, index, largerIndex);
            // 保留现场
            index = largerIndex;
            left = (index * 2) + 1;

        }
    }

    public static void heapInsert(int[] arr, int index) {
        // TOOD  / 2 <> >> 1
        while (arr[index] > arr[(index - 1) / 2]) {
            AlgorithmUtil.swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public static void main(String[] args) {
        int testTimes = 100_0000;
        int maxValue = 100;
        int maxLength = 100;
        for (int t = 0; t < testTimes; t++) {
            int[] arr = AlgorithmUtil.generateArray(maxValue, AlgorithmUtil.randomWithoutTarget(maxLength));
            int[] arr1 = AlgorithmUtil.copyArray(arr);
            int[] arr2 = AlgorithmUtil.copyArray(arr);
            int[] arr3 = AlgorithmUtil.copyArray(arr);
            heapSort(arr1);
            Arrays.sort(arr2);
            heapSort1(arr3);
            if (!AlgorithmUtil.isEquals(arr1, arr2) || !AlgorithmUtil.isEquals(arr2, arr3)) {
                AlgorithmUtil.printArray(arr);
                AlgorithmUtil.printArray(arr1);
                AlgorithmUtil.printArray(arr2);
                AlgorithmUtil.printArray(arr3);
                System.out.println("error");
                break;
            }
        }
        System.out.println("finish");
    }


    // 堆排序额外空间复杂度O(1)
    public static void heapSort1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // O(N*logN)
//		for (int i = 0; i < arr.length; i++) { // O(N)
//			heapInsert(arr, i); // O(logN)
//		}
        // O(N)
        for (int i = arr.length - 1; i >= 0; i--) {
            heapify1(arr, i, arr.length);
        }
        int heapSize = arr.length;
        swap1(arr, 0, --heapSize);
        // O(N*logN)
        while (heapSize > 0) { // O(N)
            heapify1(arr, 0, heapSize); // O(logN)
            swap1(arr, 0, --heapSize); // O(1)
        }
    }

    // arr[index]刚来的数，往上
    public static void heapInsert1(int[] arr, int index) {
        while (arr[index] > arr[(index - 1) / 2]) {
            swap1(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    // arr[index]位置的数，能否往下移动
    public static void heapify1(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1; // 左孩子的下标
        while (left < heapSize) { // 下方还有孩子的时候
            // 两个孩子中，谁的值大，把下标给largest
            // 1）只有左孩子，left -> largest
            // 2) 同时有左孩子和右孩子，右孩子的值<= 左孩子的值，left -> largest
            // 3) 同时有左孩子和右孩子并且右孩子的值> 左孩子的值， right -> largest
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            // 父和较大的孩子之间，谁的值大，把下标给largest
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest == index) {
                break;
            }
            swap1(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

    public static void swap1(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}
